SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Algorithm selection</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Algorithm selection</span></span>

</h1>

</header>

</p><p><b>Algorithm selection</b> (sometimes also called <b>per-instance algorithm selection</b> or <b>offline algorithm selection</b>) is a meta-<a href="Algorithmic_technique" title="Algorithmic technique">algorithmic technique</a> to choose an algorithm from a portfolio on an instance-by-instance basis. It is motivated by the observation that on many practical problems, different algorithms have different performance characteristics. That is, while one algorithm performs well in some scenarios, it performs poorly in others and vice versa for another algorithm. If we can identify when to use which algorithm, we can optimize for each scenario and improve overall performance. This is what algorithm selection aims to do. The only prerequisite for applying algorithm selection techniques is that there exists (or that there can be constructed) a set of complementary algorithms.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>Given a portfolio <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}}</annotation>

</semantics>

</math></span><img src="./10d6ec962de5797ba4f161c40e66dca74ae95cc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.704ex; height:2.176ex;" alt="{\displaystyle {\mathcal {P}}}" loading="lazy"></span> of algorithms <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}\in {\mathcal {P}}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}\in {\mathcal {P}}}</annotation>

</semantics>

</math></span><img src="./ed01dc144f0106846cc0b29f90233b513c5eeee5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.448ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}\in {\mathcal {P}}}" loading="lazy"></span>, a set of instances <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math></span><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"></span> and a cost metric <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R} }">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./1deb48b6ac44463025cb2532c446fd5dbaf016cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.306ex; height:2.176ex;" alt="{\displaystyle m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R} }" loading="lazy"></span>, the algorithm selection problem consists of finding a mapping <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s:{\mathcal {I}}\to {\mathcal {P}}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s:{\mathcal {I}}\to {\mathcal {P}}}</annotation>

</semantics>

</math></span><img src="./5a9751e006a70e5df098a088560a4a7748e40b0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.838ex; height:2.176ex;" alt="{\displaystyle s:{\mathcal {I}}\to {\mathcal {P}}}" loading="lazy"></span> from instances <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math></span><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"></span> to algorithms <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}}</annotation>

</semantics>

</math></span><img src="./10d6ec962de5797ba4f161c40e66dca74ae95cc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.704ex; height:2.176ex;" alt="{\displaystyle {\mathcal {P}}}" loading="lazy"></span> such that the cost <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i\in {\mathcal {I}}}m(s(i),i)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i\in {\mathcal {I}}}m(s(i),i)}</annotation>

</semantics>

</math></span><img src="./a5f87a151c656a7688529bad994d4b85bf91ae93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:13.13ex; height:5.676ex;" alt="{\displaystyle \sum _{i\in {\mathcal {I}}}m(s(i),i)}" loading="lazy"></span> across all instances is optimized.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Boolean_satisfiability_problem_(and_other_hard_combinatorial_problems)">Boolean satisfiability problem (and other hard combinatorial problems)</h3></div>

<p>A well-known application of algorithm selection is the <a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem</a>. Here, the portfolio of algorithms is a set of (complementary) <a href="SAT_solver" title="SAT solver">SAT solvers</a>, the instances are Boolean formulas, the cost metric is for example average runtime or number of unsolved instances. So, the goal is to select a well-performing SAT solver for each individual instance. In the same way, algorithm selection can be applied to many other <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {NP}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {NP}}}</annotation>

</semantics>

</math></span><img src="./87fa655c6095197732cf6223a7749d794e08697d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.062ex; width:4.04ex; height:2.509ex;" alt="{\displaystyle {\mathcal {NP}}}" loading="lazy"></span>-hard problems (such as <a href="Linear_programming" title="Linear programming">mixed integer programming</a>, <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">CSP</a>, <a href="Automated_planning_and_scheduling" title="Automated planning and scheduling">AI planning</a>, <a href="Travelling_salesman_problem" title="Travelling salesman problem">TSP</a>, <a href="MAXSAT" class="mw-redirect" title="MAXSAT">MAXSAT</a>, <a href="QBF" class="mw-redirect" title="QBF">QBF</a> and <a href="Answer_set_programming" title="Answer set programming">answer set programming</a>). Competition-winning systems in SAT are SATzilla,<sup id="cite_ref-zilla08_3-0" class="reference"><a href="#cite_note-zilla08-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> 3S<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> and CSHC<sup id="cite_ref-CSHC_5-0" class="reference"><a href="#cite_note-CSHC-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Machine_learning">Machine learning</h3></div>

<p>In <a href="Machine_learning" title="Machine learning">machine learning</a>, algorithm selection is better known as <a href="Meta-learning_(computer_science)" title="Meta-learning (computer science)">meta-learning</a>. The portfolio of algorithms consists of machine learning algorithms (e.g., Random Forest, SVM, DNN), the instances are data sets and the cost metric is for example the error rate. So, the goal is to predict which machine learning algorithm will have a small error on each data set.

</p>

<div class="mw-heading mw-heading2"><h2 id="Instance_features">Instance features</h2></div>

<p>The algorithm selection problem is mainly solved with machine learning techniques. By representing the problem instances by numerical features <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span>, algorithm selection can be seen as a <a href="Multi-class_classification" class="mw-redirect" title="Multi-class classification">multi-class classification</a> problem by learning a mapping <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}\mapsto {\mathcal {A}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{i}\mapsto {\mathcal {A}}}</annotation>

</semantics>

</math></span><img src="./d8de525b30eb1e2668041f7de6efc16595782a64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.456ex; height:2.676ex;" alt="{\displaystyle f_{i}\mapsto {\mathcal {A}}}" loading="lazy"></span> for a given instance <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>.

</p><p>Instance features are numerical representations of instances. For example, we can count the number of variables, clauses, average clause length for Boolean formulas,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> or number of samples, features, class balance for ML data sets to get an impression about their characteristics.

</p>

<div class="mw-heading mw-heading3"><h3 id="Static_vs._probing_features">Static vs. probing features</h3></div>

<p>We distinguish between two kinds of features:

</p>

<ol><li>Static features are in most cases some counts and statistics (e.g., clauses-to-variables ratio in SAT). These features ranges from very cheap features (e.g. number of variables) to very complex features (e.g., statistics about variable-clause graphs).</li>

<li>Probing features (sometimes also called landmarking features) are computed by running some analysis of algorithm behavior on an instance (e.g., accuracy of a cheap decision tree algorithm on an ML data set, or running for a short time a stochastic local search solver on a Boolean formula). These feature often cost more than simple static features.</li></ol>

<div class="mw-heading mw-heading3"><h3 id="Feature_costs">Feature costs</h3></div>

<p>Depending on the used performance metric <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math></span><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span>, feature computation can be associated with costs.

For example, if we use running time as performance metric, we include the time to compute our instance features into the performance of an algorithm selection system.

SAT solving is a concrete example, where such feature costs cannot be neglected, since instance features for <a href="Conjunctive_normal_form" title="Conjunctive normal form">CNF</a> formulas can be either very cheap (e.g., to get the number of variables can be done in constant time for CNFs in the DIMACs format) or very expensive (e.g., graph features which can cost tens or hundreds of seconds).

</p><p>It is important to take the overhead of feature computation into account in practice in such scenarios; otherwise a misleading impression of the performance of the algorithm selection approach is created. For example, if the decision which algorithm to choose can be made with perfect accuracy, but the features are the running time of the portfolio algorithms, there is no benefit to the portfolio approach. This would not be obvious if feature costs were omitted.

</p>

<div class="mw-heading mw-heading2"><h2 id="Approaches">Approaches</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Regression_approach">Regression approach</h3></div>

<p>One of the first successful algorithm selection approaches predicted the performance of each algorithm <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R} }">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./486e3f9b6a749a0a7636f278c6bb7a2c66be6efd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.34ex; height:2.509ex;" alt="{\displaystyle {\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R} }" loading="lazy"></span> and selected the algorithm with the best predicted performance <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)}">

</mrow>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)}</annotation>

</semantics>

</math></span><img src="./a48758ffefcae009c0e5c3c6adfadf8d905db0b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:14.274ex; height:4.176ex;" alt="{\displaystyle arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)}" loading="lazy"></span> for an instance <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>.<sup id="cite_ref-zilla08_3-1" class="reference"><a href="#cite_note-zilla08-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Clustering_approach">Clustering approach</h3></div>

<p>A common assumption is that the given set of instances <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math></span><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"></span> can be clustered into homogeneous subsets

and for each of these subsets, there is one well-performing algorithm for all instances in there.

So, the training consists of identifying the homogeneous clusters via an unsupervised clustering approach and associating an algorithm with each cluster.

A new instance is assigned to a cluster and the associated algorithm selected.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>A more modern approach is cost-sensitive <a href="Hierarchical_clustering" title="Hierarchical clustering">hierarchical clustering</a><sup id="cite_ref-CSHC_5-1" class="reference"><a href="#cite_note-CSHC-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> using supervised learning to identify the homogeneous instance subsets.

</p>

<div class="mw-heading mw-heading3"><h3 id="Pairwise_cost-sensitive_classification_approach">Pairwise cost-sensitive classification approach</h3></div>

<p>A common approach for multi-class classification is to learn pairwise models between every pair of classes (here algorithms)

and choose the class that was predicted most often by the pairwise models.

We can weight the instances of the pairwise prediction problem by the performance difference between the two algorithms.

This is motivated by the fact that we care most about getting predictions with large differences correct, but the penalty for an incorrect prediction is small if there is almost no performance difference.

Therefore, each instance <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> for training a classification model <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}_{1}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}_{1}}</annotation>

</semantics>

</math></span><img src="./97d7d5893bb0561776b2f3806205578a690da032.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.909ex; height:2.676ex;" alt="{\displaystyle {\mathcal {A}}_{1}}" loading="lazy"></span> vs <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}_{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}_{2}}</annotation>

</semantics>

</math></span><img src="./68792123d9a3278616d5751c2b2bb05981ff0039.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.909ex; height:2.676ex;" alt="{\displaystyle {\mathcal {A}}_{2}}" loading="lazy"></span> is associated with a cost <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|}">

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|}</annotation>

</semantics>

</math></span><img src="./aa5ffc9f3ade6b237171d889c7ea4340eb77320a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.324ex; height:2.843ex;" alt="{\displaystyle |m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|}" loading="lazy"></span>.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Requirements">Requirements</h2></div>

<p>The algorithm selection problem can be effectively applied under the following assumptions:

</p>

<ul><li>The portfolio <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}}</annotation>

</semantics>

</math></span><img src="./10d6ec962de5797ba4f161c40e66dca74ae95cc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.704ex; height:2.176ex;" alt="{\displaystyle {\mathcal {P}}}" loading="lazy"></span> of algorithms is complementary with respect to the instance set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math></span><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"></span>, i.e., there is no single algorithm <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}\in {\mathcal {P}}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}\in {\mathcal {P}}}</annotation>

</semantics>

</math></span><img src="./ed01dc144f0106846cc0b29f90233b513c5eeee5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.448ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}\in {\mathcal {P}}}" loading="lazy"></span> that dominates the performance of all other algorithms over <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math></span><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"></span> (see figures to the right for examples on complementary analysis).</li>

<li>In some application, the computation of instance features is associated with a cost. For example, if the cost metric is running time, we have also to consider the time to compute the instance features. In such cases, the cost to compute features should not be larger than the performance gain through algorithm selection.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Application_domains">Application domains</h2></div>

<p>Algorithm selection is not limited to single domains but can be applied to any kind of algorithm if the above requirements are satisfied.

Application domains include:

</p>

<ul><li>hard combinatorial problems:<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> <a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">SAT</a>, <a href="Linear_programming" title="Linear programming">Mixed Integer Programming</a>, <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">CSP</a>, <a href="Automated_planning_and_scheduling" title="Automated planning and scheduling">AI Planning</a>, <a href="Travelling_salesman_problem" title="Travelling salesman problem">TSP</a>, <a href="MAXSAT" class="mw-redirect" title="MAXSAT">MAXSAT</a>, <a href="QBF" class="mw-redirect" title="QBF">QBF</a> and <a href="Answer_Set_Programming" class="mw-redirect" title="Answer Set Programming">Answer Set Programming</a></li>

<li>combinatorial auctions</li>

<li>in machine learning, the problem is known as <a href="Meta-learning_(computer_science)" title="Meta-learning (computer science)">meta-learning</a></li>

<li>software design</li>

<li>black-box optimization</li>

<li><a href="Multi-agent_system" title="Multi-agent system">multi-agent systems</a></li>

<li>numerical optimization</li>

<li>linear algebra, differential equations</li>

<li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">evolutionary algorithms</a></li>

<li><a href="Vehicle_routing_problem" title="Vehicle routing problem">vehicle routing problem</a></li>

<li>power systems</li></ul>

<p>For an extensive list of literature about algorithm selection, we refer to a literature overview.

</p>

<div class="mw-heading mw-heading2"><h2 id="Variants_of_algorithm_selection">Variants of algorithm selection</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Online_selection">Online selection</h3></div>

<p>Online algorithm selection refers to switching between different algorithms during the solving process. This is useful as a <a href="Hyper-heuristic" title="Hyper-heuristic">hyper-heuristic</a>. In contrast, offline algorithm selection selects an algorithm for a given instance only once and before the solving process.

</p>

<div class="mw-heading mw-heading3"><h3 id="Computation_of_schedules">Computation of schedules</h3></div>

<p>An extension of algorithm selection is the per-instance algorithm scheduling problem, in which we do not select only one solver, but we select a time budget for each algorithm on a per-instance base. This approach improves the performance of selection systems in particular if the instance features are not very informative and a wrong selection of a single solver is likely.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Selection_of_parallel_portfolios">Selection of parallel portfolios</h3></div>

<p>Given the increasing importance of parallel computation,

an extension of algorithm selection for parallel computation is parallel portfolio selection,

in which we select a subset of the algorithms to simultaneously run in a parallel portfolio.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.coseal.net/aslib/">Algorithm Selection Library (ASlib)</a></li>

<li><a rel="nofollow" class="external text" href="https://larskotthoff.github.io/assurvey/">Algorithm selection literature</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRice1976" class="citation book cs1">Rice, John R. (1976). "The Algorithm Selection Problem". <a rel="nofollow" class="external text" href="https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1098&context=cstech"><i>Advances in Computers</i></a>. Vol. 15. pp. <span class="nowrap">65–</span>118. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0065-2458%2808%2960520-3">10.1016/S0065-2458(08)60520-3</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780120121151</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFBischlKerschkeKotthoffLindauer2016" class="citation journal cs1">Bischl, Bernd; Kerschke, Pascal; Kotthoff, Lars; Lindauer, Marius; Malitsky, Yuri; Fréchette, Alexandre; Hoos, Holger; Hutter, Frank; Leyton-Brown, Kevin; Tierney, Kevin; Vanschoren, Joaquin (2016). "ASlib: A benchmark library for algorithm selection". <i>Artificial Intelligence</i>. <b>237</b>: <span class="nowrap">41–</span>58. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1506.02465">1506.02465</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.artint.2016.04.003">10.1016/j.artint.2016.04.003</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:261945">261945</a>.</cite></span>

</li>

<li id="cite_note-zilla08-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-zilla08_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-zilla08_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFL._XuF._HutterH._HoosK._Leyton-Brown2008" class="citation journal cs1">L. Xu; F. Hutter; H. Hoos & K. Leyton-Brown (2008). "SATzilla: Portfolio-based Algorithm Selection for SAT". <i>Journal of Artificial Intelligence Research</i>. <b>32</b>: <span class="nowrap">565–</span>606. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1111.2249">1111.2249</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1613%2Fjair.2490">10.1613/jair.2490</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10987043">10987043</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFS._KadiogluY._MalitskyA._SabharwalH._Samulowitz2011" class="citation book cs1">S. Kadioglu; Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2011). "Algorithm Selection and Scheduling". In Lee, J. (ed.). <i>Principles and Practice of Constraint Programming</i>. Lecture Notes in Computer Science. Vol. 6876. pp. <span class="nowrap">454–</span>469. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.211.1807">10.1.1.211.1807</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-23786-7_35">10.1007/978-3-642-23786-7_35</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-23785-0</bdi>.</cite></span>

</li>

<li id="cite_note-CSHC-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-CSHC_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-CSHC_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFY._MalitskyA._SabharwalH._SamulowitzM._Sellmann2013" class="citation book cs1">Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2013). "Algorithm Portfolios Based on Cost-Sensitive Hierarchical Clustering". <i>Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence</i>. AAAI Press. pp. <span class="nowrap">608–</span>614. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-57735-633-2</bdi>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFE._NudelmanK._Leyton-BrownH._HoosA._Devkar2004" class="citation journal cs1">E. Nudelman; K. Leyton-Brown; H. Hoos; A. Devkar; Y. Shoham (2004). <a rel="nofollow" class="external text" href="https://ai.stanford.edu/~shoham/www%20papers/CP04randomsat.pdf">"Understanding Random SAT: Beyond the Clauses-to-Variables Ratio"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of CP</i>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFS._KadiogluY._MalitskyM._SellmannK._Tierney2010" class="citation journal cs1">S. Kadioglu; Y. Malitsky; M. Sellmann; K. Tierney (2010). <a rel="nofollow" class="external text" href="https://wiwi.uni-paderborn.de/fileadmin/dep3ls7/Downloads/Publikationen/PDFs/isac-ecai2010.pdf">"ISAC – Instance-Specific Algorithm Configuration"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the European Conference on Artificial Intelligence</i>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFL._XuF._HutterJ._ShenH._Hoos2012" class="citation journal cs1">L. Xu; F. Hutter; J. Shen; H. Hoos; K. Leyton-Brown (2012). <a rel="nofollow" class="external text" href="https://www.cs.ubc.ca/~kevinlb/papers/2012-SATzilla2012-Solver-Description.pdf">"SATzilla2012: Improved Algorithm Selection Based on Cost-sensitive Classification Models"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the SAT Challenge 2012: Solver and Benchmark Descriptions</i>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFA._FrechetteL._KotthoffT._MichalakT._Rahwan2016" class="citation journal cs1">A. Frechette; L. Kotthoff; T. Michalak; T. Rahwan; H. Hoos & K. Leyton-Brown (2016). <a rel="nofollow" class="external text" href="https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/download/12495/12107">"Using the Shapley Value to Analyze Algorithm Portfolios"</a>. <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. <b>30</b>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1609%2Faaai.v30i1.10440">10.1609/aaai.v30i1.10440</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6676831">6676831</a>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">Kotthoff, Lars. "<a rel="nofollow" class="external text" href="https://www.aaai.org/ojs/index.php/aimagazine/article/download/2460/2438">Algorithm selection for combinatorial search problems: A survey</a>." Data Mining and Constraint Programming. Springer, Cham, 2016. 149-190.</span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFM._LindauerR._BergdollF._Hutter2016" class="citation book cs1">M. Lindauer; R. Bergdoll; F. Hutter (2016). "An Empirical Study of Per-instance Algorithm Scheduling". <a rel="nofollow" class="external text" href="http://ml.informatik.uni-freiburg.de/papers/16-LION-ASschedules.pdf"><i>Learning and Intelligent Optimization</i></a> <span class="cs1-format">(PDF)</span>. Lecture Notes in Computer Science. Vol. 10079. pp. <span class="nowrap">253–</span>259. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-50349-3_20">10.1007/978-3-319-50349-3_20</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-50348-6</bdi>.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFM._LindauerH._HoosF._Hutter2015" class="citation book cs1">M. Lindauer; H. Hoos & F. Hutter (2015). "From Sequential Algorithm Selection to Parallel Portfolio Selection". <a rel="nofollow" class="external text" href="https://ml.informatik.uni-freiburg.de/papers/15-LION-ParallelAS.pdf"><i>Learning and Intelligent Optimization</i></a> <span class="cs1-format">(PDF)</span>. Lecture Notes in Computer Science. Vol. 8994. pp. <span class="nowrap">1–</span>16. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-19084-6_1">10.1007/978-3-319-19084-6_1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-19083-9</bdi>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-04-03" href="https://en.wikipedia.org/wiki/?title=Algorithm_selection&oldid=1217120227">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>